package com.leet.code.simple_array;

/**
 * @description:    1365.有多少小于当前数字的数字
 * @author: WYG
 * @time: 2021/1/3 14:07
 */

public class SmallerNumbersThanCurrent {
    //双重for循环,每次都遍历除了当前元素之外的所有元素
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int size = nums.length;
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            int temp = 0;
            for (int j = 0; j < size; j++) {
                if (i != j && nums[i] > nums[j]) {
                    temp++;
                }
            }
            res[i] = temp;
        }
        return res;
    }

    //使用桶排序
    public int[] faster_smallerNumbersThanCurrent(int[] nums) {
        int[] res = new int[nums.length];
        int[] elements = new int[101];
        for (int x : nums) {
            elements[x]++;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i]; j++) {
                res[i] += elements[j];
            }
        }
        return res;
    }

}
